# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=10
    
    The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

    Find the sum of all the primes below two million.
    
    Performance:
    time <function solution at 0x7fc7b413a7d0>: 6.402341
    time <function eratosthenes_solution at 0x7fc7b413a8c0>: 21.554518
"""
#
# Import
#
import time
import re
import math


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected):
    assert value == expected, "value %s != expected %s" % (
        value, expected)


#
# Test Case / Solution
#
@timeit    
def test_case():
    limit = 10
    expected = 17
    
    primes = prime_sieve(limit)
    assert_match(sum(primes), expected)
    
    primes = eratosthenes_sieve(limit)
    assert_match(sum(primes), expected)

    print "test case passed!"

@timeit
def solution():
    limit = 2000000
    return sum(prime_sieve(limit))
    
@timeit
def eratosthenes_solution():
    limit = 2000000
    return sum(eratosthenes_sieve(limit))


#
# Support Code
#
def prime_sieve(limit):
    primes = [2]
    
    for n in range(3, limit+1, 2):
        is_prime = True
        for prime in primes:
            
            if n % prime == 0:
                is_prime = False
                break
            
            # originally this was prime*2; this change reduced runtime of
            # solution from over 19 mins to ~6 secs.
            if prime**2 > n:
                break
            
        if is_prime:
            primes.append(n)
            #print len(primes), "found at", n
    
    return primes


def eratosthenes_sieve(limit):
    """http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes"""
    sieve = [2] + range(3, limit+1, 2)
    index = 0
    stop = int(math.floor(math.sqrt(limit)))
    
    while sieve[index] <= stop:
        index += 1
        
        if sieve[index] == 0:
            continue
        else:
            prime = sieve[index]
            #print prime
            
        for n in range(index+1, len(sieve)):
            # this line makes it twice as fast
            if sieve[n] == 0:
                continue
            
            # originally removed items from sieve, but that's slooooow
            if sieve[n] % prime == 0:
                sieve[n] = 0
                
    return sieve
    
    


#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    print eratosthenes_solution()
    